package org.example.leetcode;


import java.util.Arrays;

/**
 * @author: lynn
 * @Descript: 在排序数组中查找元素的第一个和最后一个位置
 * @Link
 * @date: 2021/8/3 11:33
 * @version: 1.0
 */
public class LC34 {
    public static void main(String[] args) {
        LC34 lc=new LC34();
        int[] nums={5,7,7,8,8,10};
        int target=8;
        System.out.println(Arrays.toString(lc.searchRange(nums,target)));
    }
    //fixme 二分法要写好
    public int[] searchRange(int[] nums, int target) {
        int[] res=new int[]{-1,-1};
        if (nums.length==0 ) return res;
        int l=0;
        int r=nums.length-1;
        while (l<=r){
            int m=l+(r-l)/2;
            if (nums[m]<target){
                l=m+1;
            }else if (nums[m]>target){
                r=m-1;
            }else {
                int lm=m;
                int rm=m;
                while (l<lm && nums[lm]==nums[lm-1]){
                    lm=lm-1;
                }
                res[0]=lm;
                while (rm<r && nums[rm]==nums[rm+1]){
                    rm=rm+1;
                }
                res[1]=rm;
                break;
            }
        }
        return res;
    }
}
